//
//  heapManager.cpp
//  DataStructureProject
//
//  Created by zhangbaochuan on 2020/4/9.
//  Copyright © 2020 Geex. All rights reserved.
//

#include <algorithm>
#include <string>
#include <ctime>
#include <cmath>
#include <cassert>
#include <sstream>
#include <sys/types.h>
#include <sys/stat.h>
#include <dirent.h>
#include <cstddef>
#include <iostream>
#include <fstream>

#include "heapManager.hpp"

#pragma mark -HeapBase

void HeapBase::testPrint(int *arr, std::string filename, int cn){
    
    std::string dotPath = CURRENT_PATH;
    std::string dotStr = "\ndigraph heap {\nnode[shape=circle];\nnodesep=0.3;\n";
    
    for (int i = 1; i <= cn; i++) {
        int leftIndex = 2 * i;
        int rightIndex = 2 * i + 1;
        
        if (leftIndex <= cn) {
            std::stringstream fmt;
            fmt << "\t" << arr[i] << "->" << arr[leftIndex] << ";\n";
            dotStr.append(fmt.str());
        }
        if (rightIndex <= cn) {
            std::stringstream fmt;
            fmt << "\t" << arr[i] << "->" << arr[rightIndex] << ";\n";
            dotStr.append(fmt.str());
        }
    }
    
    dotStr.append("}\n");
    
    std::cout << dotStr << std::endl;
    const char *path = dotPath.c_str();
    if(NULL == opendir(path)) {
       mkdir(path,0775);
    }
    std::stringstream fmt;
    fmt << dotPath << "/"<< filename <<".dot";
    const char *filePath = fmt.str().c_str();
    std::ofstream mcfile; //创建个对象
    mcfile.open(filePath,std::ios::out); //创建文件
    mcfile << dotStr;  //写入内容
    mcfile.close(); //关闭
    
    std::stringstream shell;
    shell << "/usr/local/bin/dot -Tpng " << "'" << filePath << "' " << "-o " << "'" << path << "/"<< filename <<".png" << "'";
    system(shell.str().c_str());
}

void HeapBase::testPrint() {
    
}

#pragma mark - MaxHeap

//堆第一个为数组0
void MaxHeap::shiftUp(int k) {
//    while (k > 1) {
//        int parent = (k)/2;
//        if (data[k] > data[parent]) {
//            std::swap(data[k], data[parent]);
//            k = parent;
//        }else {
//            break;
//        }
//    }
    
    while (k > 1 && data[k] > data[k/2]) {
        std::swap(data[k], data[k/2]);
        k = k/2;
    }
}

#pragma mark-- 移除最大值
int MaxHeap::extraMax() {
    int temp = data[1];
    data[1] = data[count];
    count--;
    shiftDown(1);
    return temp;
}

#pragma mark - shifDown

//当shifup 把最大值和最后一个交换时，然后移除最大值，然后shifdown 重新排序
void MaxHeap::shiftDown(int k) {
    //递归
//    int l = 2 * k;
//    int r = 2 * k + 1;
//    int max = k;
//    if (l <= count && data[max] < data[l]) {
//        max = l;
//    }
//    if (r <= count && data[max] < data[r]) {
//        max = r;
//    }
//    if (max != k) {
//        std::swap(data[max], data[k]);
//        shiftDown(max);
//    }
    
    //非递归
    while (2 * k + 1 <= count) {
        int l = k * 2;
        if (l + 1 <= count && data[l] < data[l + 1]) {
            l++;
        }
        if(data[k] > data[l]){
            return;
        }else {
            std::swap(data[k], data[l]);
            k = l;
        }
    }
    
}


MaxHeap:: MaxHeap(int capacity) {
    data = new int[capacity + 1];
    count = 0;
}

MaxHeap:: ~MaxHeap() {
    delete [] data;
}

int MaxHeap::size() {
    return count;
}

bool MaxHeap::isEmpty() {
    return count == 0;
}

void MaxHeap::insert(int v) {
    data[count + 1] = v;
    count ++;
    shiftUp(count);
}

void MaxHeap::testPrint() {
    HeapBase::testPrint(data, "MaxHeap", count);
}

void MaxHeap::testShiftDownPrint() {
    HeapBase::testPrint(data, "MaxShiftDown", count);
}

#pragma mark --heapify

Heapify:: Heapify(int arr[], int capacity) {
    
}


